﻿#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        unordered_map<int, int> hash;
        hash[0] = -1; // 默认有⼀个前缀和为 0 的情况
        int sum = 0, ret = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i] == 0 ? -1 : 1; // 计算当前位置的前缀和
            if (hash.count(sum))
                ret = max(ret, i - hash[sum]);
            else
                hash[sum] = i;
        }
        return ret;
    }
};
class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        hash[0 % k] = 1; // 0 这个数的余数
        int sum = 0, ret = 0;
        for (auto x : nums) {
            sum += x;                  // 算出当前位置的前缀和
            int r = (sum % k + k) % k; // 修正后的余数
            if (hash.count(r))
                ret += hash[r]; // 统计结果
            hash[r]++;
        }
        return ret;
    }
};
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        // lprod 表⽰：[0, i - 1] 区间内所有元素的乘积
        // rprod 表⽰：[i + 1, n - 1] 区间内所有元素的乘积
        int n = nums.size();
        vector<int> lprod(n + 1), rprod(n + 1);
        lprod[0] = 1, rprod[n - 1] = 1;

        // 预处理前缀积以及后缀积
        for (int i = 1; i < n; i++)
            lprod[i] = lprod[i - 1] * nums[i - 1];
        for (int i = n - 2; i >= 0; i--)
            rprod[i] = rprod[i + 1] * nums[i + 1];

        // 处理结果数组
        vector<int> ret(n);
        for (int i = 0; i < n; i++)
            ret[i] = lprod[i] * rprod[i];
        return ret;
    }
};